The present application claims priority under 35 U.S.C. xc2xa7119 to U.S. Provisional Patent Application No. 60/110,444, filed Nov. 27, 1998.
The present invention generally relates to error handling in the field of communication systems and, more particularly, to error handling using both automatic repeat request (ARQ) and variable rate transmission techniques in digital communication systems.
Variable rate transmission in a radio communication system can be achieved using several methods. For example, in a CDMA (Code Division Multiple Access) system the information transmission rate changes as a function of the spreading factor used for transmissions. In a TDMA (Time Division Multiple Access) system, variable rate transmission is generally achieved by using different numbers of time slots. In a TDMA system the data transmission rate also varies as a function of the modulation and coding scheme used for mapping data bits to channel bits/symbols.
EDGE Enhanced Data Rates for Global Evolution) is an example of a system that uses different modulation and coding schemes, in addition to a variable number of time slots, to achieve different transmission rates of user data. The different modulation and coding schemes used in the EDGE system, MCS-1 through MCS-6, have various payload sizes, differing for example in increments of 25 octets as shown in FIG. 1. FIG. 2 summarizes the different block sizes, code rates, and payload sizes for the different modulation and coding schemes MCS-1 through MCS-6. As indicated in FIG. 2, the modulation schemes can include PSK (Phase Shift Keying) and GMSK (Gaussian Minimum Shift Keying).
A block numbering scheme depending upon a payload in a block is disclosed in co-pending U.S. patent application Ser. No. 09/120,163, entitled xe2x80x9cMethod and Apparatus for Minimizing Overhead in a Communication Systemxe2x80x9d, which is hereby incorporated by reference. The basic principle of the numbering scheme is illustrated in FIG. 3.
As shown in FIG. 3, the block sequence numbers (SNs) can be integer multiples of an identification number of a currently used modulation and coding scheme, or can be separated by a step equal in magnitude to the identification number. For example, as shown in FIG. 3, where the current modulation and coding scheme is MCS-6, blocks in a sequence can be assigned sequence numbers 6, 12 and 18. The round trip time (RTT) shown in FIG. 3 refers to an amount of time that elapses between when one or more blocks are sent, and when acknowledgment for them is received. As shown in FIG. 3, the payload size of a block for a current modulation and coding scheme can be defined as a number of octets that is equal to a product of the identification number of the current modulation and coding scheme and a block size increment between modulation and coding schemes. For example, the block payload size of the MCS-6 modulation and coding scheme can be defined as (6)(25) octets=150 octets large.
When blocks of data are to be retransmitted at a rate that is lower than a rate at which the blocks of data were initially transmitted, the initially transmitted data can be resegmented into different size blocks, or different blocks having different payload sizes, and the different size blocks can be renumbered accordingly. For example, as shown in FIG. 3, block 12 of the MCS-6 scheme, containing a payload of 150 octets, can be resegmented into two blocks 9 and 12 each containing a payload of 75 octets, and then retransmitted in accordance with the MCS-3 scheme.
This procedure can be repeated as necessary or appropriate. If, for example, as shown in FIG. 3, the retransmitted block 9 is not correctly received, then it can be resegmented into three blocks 7, 8 and 9 each containing a payload of 25 octets in accordance with the MCS-1 scheme, and resent as the new blocks 7, 8 and 9.
Using the technique illustrated in FIG. 3, data can be retransmitted using a modulation and coding scheme that is appropriate at the time of retransmission. For example, the data can be retransmitted using a modulation and coding scheme that is optimal, and/or better at the time of the retransmission than the scheme used for the initial or previous transmission of the data.
Multiple blocks of data can also be resegmented into a fewer number of blocks for retransmission. For example, as shown in FIG. 4, where two blocks 4 and 6 of the scheme MCS-2 are corrupted and need to be retransmitted, and at the time of retransmission the scheme MCS-4 is optimal or otherwise appropriate, the two blocks 4 and 6 of the MCS-2 scheme can be combined to form the single block 6 of the scheme MCS-4 and retransmitted accordingly. The payload of the MCS-4 scheme block 6 can be formed by concatenating the payloads of the blocks 4 and 6 of the MCS-2 scheme. Note that when the optimal initial coding scheme is changed from MCS-2 to MCS-4 and the two blocks are combined, the resulting concatenated block is identified with the sequence number 6 of the second block. Alternatively, when a series of blocks are combined, the resulting combined block can be identified with the sequence number of any appropriate block in the series. For example, the combined block can be identified with the sequence number of the first block in the series, or the sequence number of the middle block, and so forth.
As shown in FIG. 5, ACK/NACK (positive acknowledgment/negative acknowledgment) messages can include a Received Block Bitmap (RBB) field format 506 having a Start Sequence Number (SSN) 502 followed by a bitmap 504. The bitmap 504 contains an acknowledgment for each possible sequence number in a sequence of data blocks starting with a block whose SN has the same value as that of the SSN 502. Thus, when this technique is used, a receiver must positively or negatively acknowledge all sequence numbers represented in an RBB field having the format 506, regardless of whether all of the sequence numbers are actually used to transmit data blocks.
FIG. 6 shows an RBB field 606 having the format 506. A single bit in the bitmap 506 can be used to acknowledge a block. Block sequence numbers of blocks acknowledged in the bitmap 506 correspond to bits in the bitmap 506 in a left-to-right, top-to-bottom order. The bitmap 506 includes a bit for each possible sequence number between the beginning and ending block sequence numbers of an ordered sequence of blocks. In other words, bits in the bitmap represent or acknowledge blocks having sequence numbers that are separated by a minimum step, regardless of whether the step in a particular ordered sequence of blocks is greater than the minimum step. Thus, both used and unused SNs are represented or acknowledged in the bitmap 506.
For example, as shown in FIG. 6, when the RBB field 606 is used to indicate the acknowledgment status of a 12-block sequence that is configured in accordance with the MCS-3 scheme (so that the SNs of the blocks in the 12-block sequence are separated by a step of 3), every third bit in the bitmap 506 indicates the acknowledgment status of a block in a 12-block sequence. As shown in FIG. 6, the sequence starts (as indicated by the SSN 602) with data block 15, and includes blocks having SNs of 15, 18, 21, 24, 27, 30, 33, 36, 39, 42, 45 and 48. As shown in FIG. 6, blocks having SNs of 15, 18, 30 and 39 are each represented by three bits having a zero value, indicating that the blocks having SNs of 15, 18, 30 and 39 are negatively acknowledged (NACKed) and need to be retransmitted. However, unused SNs of 16, 17, 19, 20, 22, 23, 26, 26, 28, 29, 31, 32, 34, 35, 37, 38, 40, 41, 43, 44, 46, 47, 49 and 50 are also acknowledged. Thus, a total of (3)(12)=36 bits in the bitmap 604 are required to indicate the acknowledgment status of a 12-block sequence configured in accordance with the MCS-3 scheme. Other schemes can require even more bits in the bitmap. For example, if a 12-block sequence were configured in accordance with the MCS-6 scheme, a total of (6)(12)=72 bits would be required in the bitmap to acknowledge the 12-block sequence.
In summary, the RBB format shown in FIG. 5 is poorly suited for positively and negatively acknowledging transmitted blocks in a system that uses variable rate data transmission, and skips block sequence numbers depending on the rate used. For example, in situations where the MCS-6 scheme is used and N blocks in a consecutive sequence bear the sequence numbers {6, 12, 18, . . . 6*N}, the RBB format would require a separate acknowledgment for each of sequence numbers {1, 2, 3, 4, 5, . . . 6*N}, even though only the sequence numbers {6, 12, 18, . . . 6*N} need to be considered. Thus, the RBB format requires unnecessarily large overheads when used in a system that employs variable rate data transmission and skips block sequence numbers depending on the rate used.
Accordingly, a need exists for an efficient, low-overhead method and technique for positively and negatively acknowledging transmitted blocks in a system that employs variable rate data transmission and skips block sequence numbers depending on the rate used.
In accordance with various exemplary embodiments of the invention, a method and technique are provided for efficiently acknowledging transmitted information in a system that employs variable rate data transmission, and skips data block sequence numbers depending on the transmission rate used. In accordance with exemplary embodiments of the invention, the ACK/NACK overhead in a variable rate communication system is reduced by providing an RBB format that is more compact and which can therefore be transmitted and evaluated in less time. This conserves time and computing resources, and allows data to be retransmitted with less delay. In other words, exemplary embodiments of the invention reduce an amount of time between a first transmission of data and a subsequent retransmission of the data.
In accordance with exemplary embodiments of the invention, in a system that employs variable rate data transmission and skips block sequence numbers depending on the data transmission rate used, the skipped block sequence numbers are not acknowledged, thus reducing RBB field sizes in ACK/NACK messages used in the system.
In accordance with an exemplary embodiment of the invention, an RBB field in an ACK/NACK message includes a starting sequence number, an indication of a sequence number step, and a bitmap. The starting sequence number indicates a first block in a series of transmitted blocks that are being acknowledged via the ACK/NACK message. The sequence number step is a minimum difference between sequence numbers of blocks in the series. Where the series is ordered, the sequence number step is a difference between the sequence numbers of adjacent or consecutive blocks in the series. The bitmap can be configured so that each bit in the bitmap represents an acknowledgment of one of the blocks in the series.
In accordance with another exemplary embodiment of the invention, the RBB field in the ACK/NACK message includes multiple starting sequence numbers, and both a sequence number step and a length for each starting sequence number. Each set of starting sequence number, sequence number step and length indicates a subseries or subsequence of the series of transmitted blocks that is being acknowledged via the ACK/NACK message. The starting sequence number indicates a sequence number of a first block in the subsequence, the length indicates how many blocks are in the subsequence, and the sequence number step indicates a difference between sequence numbers of adjacent blocks in the subsequence.